#include <vector>
class Solution {
public:
    vector<int> find(TreeNode* root, int target)
    {
        vector<int> path;
        while (root->val != target)
        {
            path.push_back(root->val);
            if (target < root->val)
                root = root->left;
            else
                root = root->right;
        }
        path.push_back(root->val);
        return path;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q)
    {
        vector<int> p_get = find(root, p);
        vector<int> q_get = find(root, q);
        int res = 0;
        for (int i = 0; i < p_get.size() && i < q_get.size(); i++)
        {
            if (p_get[i] == q_get[i])
                res = p_get[i];
            else
                break;
        }
        return res;
    }
};